package graphen.struktur;
import java.util.StringTokenizer;
import java.util.Vector;

/**
 * Diese Klasse verwaltet einen Graphen mit seinen Knoten und Kanten.
 * Weil die Knoten nach ihrem Namen unterschieden werden, gibt es keine zwei
 * Knoten mit dem gleichen Inhalt.
 */
public class Graph {
  Vector<Knoten> knoten;
  
  /**
   * Erzeugt einen leeren Graphen.
   */
  public Graph(){
    knoten=new Vector<Knoten>();
  }
  
  /**
   * Erzeugt einen Graphen aus einem String, der die Struktur angibt.
   * Z.B. erzeugt der String "A-B,A-C/20" die drei Knoten A, B und C.
   * Von A nach B weist eine Kante mit dem Defaultwert 50. Von A nach
   * C weist eine Kante mit dem angegebenen Wert 20. Von B nach A und
   * von C nach A weisen keine Kanten.
   * @param edges der String der die Struktur des Graphen definiert.
   */
  public Graph(String edges){
    knoten=new Vector<Knoten>();
    for(StringTokenizer t=new StringTokenizer(edges, ","); t.hasMoreTokens();){
      String str=t.nextToken();
      int i=str.indexOf('-');
      if(i>0){
        int len=0;
        int j=str.indexOf('/');
        if (j>0) {
          len=Integer.valueOf(str.substring(j+1)).intValue();
          str=str.substring(0, j);
        }
        addKante(str.substring(0,i), str.substring(i+1), len);
      }
    }
  }
  
  /**
   * Gibt die Anzahl der Knoten dieses Graphen zurück.
   * @return die Anzahl der Knoten dieses Graphen.
   */
  public int anzKnoten(){
    return knoten.size();
  }
  
  /**
   * Fügt diesem Graphen einen Knoten hinzu. Wenn ein Knoten mit diesem
   * Namen schon existiert, passiert nichts.
   * @param label der Name des neuen Knoten
   */
  public void addKnoten(String label){
    Knoten k=sucheKnoten(label);
    if(k==null){
      k=new Knoten(label);
      knoten.add(k);
    }
  }
  
  /**
   * Fügt dem Graphen eine gewichtete Kante zwischen zwei Knoten hinzu.
   * @param von der Knoten, von dem die Kante ausgeht.
   * @param nach der Knoten, zu dem die Kante verläuft.
   * @param kosten die Gewichtung dieser Kante.
   */
  public void addKante(String von, String nach, int kosten){
    addKnoten(von);
    addKnoten(nach);
    Knoten a=sucheKnoten(von);
    Knoten b=sucheKnoten(nach);
    a.addKante(b, kosten);
  }
  
  Knoten sucheKnoten(String la){
    int i=sucheKnotenNr(la);
    if(i<0) return null;
    else return knoten.get(i);
  }
  
  /**
   * Sucht den Knoten mit einer bestimmten Namen und liefert seine
   * Nummer zurück.
   * @param la der Name des Knoten, dessen Nummer gesucht wird.
   * @return seine Nummer, oder -1, falls er nicht gefunden wird.
   */
  public int sucheKnotenNr(String la){
    for(int i=0; i<knoten.size(); ++i){
      Knoten k=knoten.get(i);
      if(k.label.equals(la)) return i;
    }
    return -1;
  }
  
  /**
   * Entfernt aus diesem Graphen einen Knoten.
   * @param la der Name des zu entfernenden Knoten.
   */
  public void removeKnoten(String la){
    Knoten k=sucheKnoten(la);
    knoten.remove(k);
    for(int i=0; i<knoten.size(); ++i)
      knoten.get(i).removeKante(k);
  }
  
  /**
   * Entfernt aus diesem Graphen eine Kante.
   * @param von der Name des Knoten, von dem die Kante ausgeht.
   * @param nach der Name des Knoten, bei dem die Kante endet.
   */
  public void removeKante(String von, String nach){
    Knoten a=sucheKnoten(von);
    if(a==null) return;
    Knoten b=sucheKnoten(nach);
    a.removeKante(b);
  }

  /**
   * Gibt ein Array mit allen Knotennamen dieses Graphen zurück.
   * @return das Array mit den Namen aller Knoten in diesem Graphen.
   */
  public String[] alleKnotennamen(){
    int anz=knoten.size();
    String[] ret=new String[anz];
    for(int i=0; i<anz; ++i){
      Knoten k=knoten.get(i);
      ret[i]=k.label;
    }
    return ret;
  }
  
  int[] alleZieleVon(Knoten k){
    int anz=k.kanten.size();
    int[] ret=new int[anz];
    for(int i=0; i<anz; ++i){
      Knoten f=k.kanten.get(i).ziel;
      ret[i]=knoten.indexOf(f);
    }
    return ret;
  }

  /**
   * Gibt die Indizes aller Knoten zurück, auf die Kanten von einem
   * gegebenen Knoten zeigen. Um von den Indizes auf die Namen der
   * Knoten zu schließen, kann damit auf das Ergebnis von <CODE>alleKnotennamen</CODE>
   * zugegriffen werden.
   * @param label der Name des Knoten, von dem die Kanten ausgehen.
   * @return die Menge aller Zielknotenindizes.
   */
  public int[] alleZieleVon(String label){
    Knoten k=sucheKnoten(label);
    return alleZieleVon(k);
  }

  /**
   * Gibt die Indizes aller Knoten zurück, auf die Kanten von einem
   * gegebenen Knoten zeigen. Um von den Indizes auf die Namen der
   * Knoten zu schließen, kann damit auf das Ergebnis von <CODE>alleKnotennamen</CODE>
   * zugegriffen werden.
   * @param nr der Index des Knoten, von dem die Kanten ausgehen.
   * @return die Menge aller Zielknotenindizes.
   */
  public int[] alleZieleVon(int nr){
    Knoten k=knoten.get(nr);
    return alleZieleVon(k);
  }

  int getKosten(Knoten von, Knoten nach){
    Kante e=von.getKanteZu(nach);
    if(e==null) return -1;
    else return e.kosten;
  }

  /**
   * Gibt die Gewichtung einer Kante zwischen zwei gegebenen Knoten zurück.
   * @param von der Name des Knoten, von dem die Kante ausgeht.
   * @param nach der Name des Knoten, bei dem die Kante endet.
   * @return das Gewicht dieser Kante oder -1, falls es keine Kante gibt.
   */
  public int getKosten(String von, String nach){
    return getKosten(sucheKnoten(von),sucheKnoten(nach));
  }

  /**
   * Gibt die Gewichtung einer Kante zwischen zwei gegebenen Knoten zurück.
   * @param von der Index des Knotens, von dem die Kante ausgeht.
   * @param nach der Index des Knotens, bei dem die Kante endet.
   * @return das Gewicht dieser Kante oder -1, falls es keine Kante gibt.
   */
  public int getKosten(int von, int nach){
    return getKosten(knoten.get(von),knoten.get(nach));
  }

  /**
   * Gibt eine Wegbeschreibung vom angegebenen Knoten aus zu allen
   * erreichbaren Knoten zurück.
   * @param startnr der Index des Startknotens, von dem alle Wege ausgehen.
   * @return die Wegbeschreibung zu allen erreichbaren Zielen.
   */
  public Plan getPlan(int startnr){
    return new Plan(startnr);
  }

  /**
   * Gibt eine Wegbeschreibung vom angegebenen Knoten aus zu allen
   * erreichbaren Knoten zurück.
   * @param label Name des Startknotens, von dem alle Wege ausgehen.
   * @return die Wegbeschreibung zu allen erreichbaren Zielen.
   */
  public Plan getPlan(String label){
    return getPlan(sucheKnotenNr(label));
  }

  /**
   * Ein Plan ist die Zusammenfassung aller kürzesten Wege von einem
   * bestimmten Startknoten aus. Alle Angaben werden durch ganze Zahlen
   * getätigt; diese Zahlen stehen immer für den Index des entsprechenden
   * Knotens im Graphen.
   */
  public class Plan{
    int startknoten;
    int[] vaternr;
    int[] abstand;

    /**
     * Erzeugt eine vollständige Wegbeschreibung von einem gegebenen
     * Startknoten aus.
     * @param a der Index des Startknotens.
     */
    public Plan(int a){
      startknoten=a;
      int len=knoten.size();
      vaternr=new int[len];
      abstand=new int[len];
      boolean[] fertig=new boolean[len];
      for(int i=0; i<len; ++i)
        if(i!=a){
          vaternr[i]=-1;
          abstand[i]=-1;
        }
      abstand[a]=vaternr[a]=0;
      do{
        fertig[a]=true;
        for(Kante ka: knoten.get(a).kanten){
          int zielnr=knoten.indexOf(ka.ziel);
          if(fertig[zielnr]) continue;
          else{
            int neudist=abstand[a]+ka.kosten;
            if(vaternr[zielnr]<0 || neudist<abstand[zielnr]){
              vaternr[zielnr]=a;
              abstand[zielnr]=neudist;
            }
          }
        }
        // suche nächsten gelben Knoten, speichere in a
        int min=Integer.MAX_VALUE;
        a=-1;
        for(int i=0; i<len; ++i)
          if(!fertig[i] && abstand[i]>-1 && abstand[i]<min){
            min=abstand[i];
            a=i;
          }
      } while(a>-1);
    }

    /**
     * Gibt einen kürzesten Weg zu dem angegebenen Knoten zurück.
     * Der Weg ist eine Folge von Indizes auf die der Reihe nach
     * anzugehenden Knoten.
     * @param n der Index des Knotens, der erreicht werden soll.
     * @return das Array von Indizes der anzugehenden Knoten einschließlich
     * Start- und Zielknoten. Existiert kein Weg, so hat das Array
     * die Länge 0.
     */
    public int[] getWegNach(int n){
      if(vaternr[n]==-1) return new int[0];
      int anz=1;
      int m=n;
      while(m!=startknoten){
        anz++;
        m=vaternr[m];
      }
      int[] ret=new int[anz];
      for(int i=anz-1; i>=0; --i){
        ret[i]=n;
        n=vaternr[n];
      }
      return ret;
    }

    /**
     * Gibt an, welcher Knoten der Startknoten aller Wege dieses Plans ist.
     * @return der Index des Startknotens aller Wege dieses Plans.
     */
    public int getStartNr(){
      return startknoten;
    }
    
    /**
     * Gibt den Abstand eines Knotens vom Startknoten an.
     * @param n die Nummer des Knotens, dessen Abstand vom Startknoten gesucht
     *   ist.
     * @return der Abstand vom Startknoten oder -1, falls es keinen Weg gibt.
     */
    public int getAbstand(int n){
      return this.abstand[n];
    }

    /**
     * Gibt die Folge aller Knotennamen auf dem Weg zu dem angegebenen
     * Knoten zurück. Die Namen sind getrennt durch das Zeichen "-".
     * @param n der Zielknotenindex.
     * @return die Folge von Knotennamen vom Start (eingeschlossen) bis
     * zum Ziel (eingeschlossen). Existiert kein Weg, so wird
     * kein Wert (<CODE>null</CODE>) zurück gegeben.
     */
    public String getWegNamenNach(int n){
      int[] weg=getWegNach(n);
      StringBuffer sb=new StringBuffer();
      for(int i=0, anz=weg.length; i<anz; ++i){
        sb.append(knoten.get(weg[i]).label);
        if(i<anz-1) sb.append("-");
      }
      return sb.toString();
    }
  }
}